{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #夺回据点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #array #biconnected-component"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #数组 #双连通分量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #夺回据点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣城，本次试炼主题为「夺回据点」。\n",
    "\n",
    "魔物了占领若干据点，这些据点被若干条道路相连接，`roads[i] = [x, y]` 表示编号 `x`、`y` 的两个据点通过一条道路连接。\n",
    "\n",
    "现在勇者要将按照以下原则将这些据点逐一夺回：\n",
    "\n",
    "- 在开始的时候，勇者可以花费资源先夺回一些据点，初始夺回第 `j` 个据点所需消耗的资源数量为 `cost[j]` \n",
    "\n",
    "- 接下来，勇者在不消耗资源情况下，每次可以夺回**一个**和「已夺回据点」相连接的魔物据点，并对其进行夺回\n",
    "\n",
    "> 注：为了防止魔物暴动，勇者在每一次夺回据点后（包括花费资源夺回据点后），需要保证剩余的所有魔物据点之间是相连通的（不经过「已夺回据点」）。\n",
    "\n",
    "请返回勇者夺回所有据点需要消耗的最少资源数量。\n",
    "\n",
    "**注意：**\n",
    "- 输入保证初始所有据点都是连通的，且不存在重边和自环\n",
    "\n",
    "**示例 1：**\n",
    ">输入：\n",
    ">`cost = [1,2,3,4,5,6]`\n",
    ">`roads = [[0,1],[0,2],[1,3],[2,3],[1,2],[2,4],[2,5]]`\n",
    ">\n",
    ">输出：`6`\n",
    ">\n",
    ">解释：\n",
    ">勇者消耗资源 `6` 夺回据点 `0` 和 `4`，魔物据点 `1、2、3、5` 相连通；\n",
    ">第一次夺回据点 `1`，魔物据点 `2、3、5` 相连通；\n",
    ">第二次夺回据点 `3`，魔物据点 `2、5` 相连通；\n",
    ">第三次夺回据点 `2`，剩余魔物据点 `5`；\n",
    ">第四次夺回据点 `5`，无剩余魔物据点；\n",
    ">因此最少需要消耗资源为 `6`，可占领所有据点。\n",
    "![image.png](https://pic.leetcode-cn.com/1648706944-KJstUN-image.png){:height=170px}\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：\n",
    ">`cost = [3,2,1,4]`\n",
    ">`roads = [[0,2],[2,3],[3,1]]`\n",
    ">\n",
    ">输出：`2`\n",
    ">\n",
    ">解释：\n",
    ">勇者消耗资源 `2` 夺回据点 `1`，魔物据点 `0、2、3` 相连通；\n",
    ">第一次夺回据点 `3`，魔物据点 `2、0` 相连通；\n",
    ">第二次夺回据点 `2`，剩余魔物据点 `0`；\n",
    ">第三次夺回据点 `0`，无剩余魔物据点；\n",
    ">因此最少需要消耗资源为 `2`，可占领所有据点。\n",
    "![image.png](https://pic.leetcode-cn.com/1648707186-LJRwzU-image.png){:height=60px}\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= roads.length, cost.length <= 10^5`\n",
    "- `0 <= roads[i][0], roads[i][1] < cost.length`\n",
    "- `1 <= cost[i] <= 10^9`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [s5kipK](https://leetcode.cn/problems/s5kipK/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [s5kipK](https://leetcode.cn/problems/s5kipK/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6]\\n[[0,1],[0,2],[1,3],[2,3],[1,2],[2,4],[2,5]]', '[3,2,1,4]\\n[[0,2],[2,3],[3,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.S = 0\n",
    "        self.e = []\n",
    "        self.isCut = []\n",
    "        self.dfn = []\n",
    "        self.low = []\n",
    "        self.clk = 0\n",
    "        self.stk = []\n",
    "        self.dcc = []\n",
    "\n",
    "    def tarjan(self, sn):\n",
    "        self.dfn[sn] = self.low[sn] = self.clk + 1\n",
    "        self.clk += 1\n",
    "        self.stk.append(sn)\n",
    "        flag = 0\n",
    "        for fn in self.e[sn]:\n",
    "            if not self.dfn[fn]:\n",
    "                self.tarjan(fn)\n",
    "                self.low[sn] = min(self.low[sn], self.low[fn])\n",
    "                if self.low[fn] >= self.dfn[sn]:\n",
    "                    flag += 1\n",
    "                    if sn != self.S or flag > 1:\n",
    "                        self.isCut[sn] = True\n",
    "                    t = -1\n",
    "                    new_dcc = []\n",
    "                    while t != fn:\n",
    "                        t = self.stk.pop()\n",
    "                        new_dcc.append(t)\n",
    "                    new_dcc.append(sn)\n",
    "                    self.dcc.append(new_dcc)\n",
    "            else:\n",
    "                self.low[sn] = min(self.low[sn], self.dfn[fn])\n",
    "\n",
    "    def minimumCost(self, cost, roads):\n",
    "        n = len(cost)\n",
    "        if n == 1:\n",
    "            return cost[0]\n",
    "\n",
    "        self.e = [[] for _ in range(n)]\n",
    "        for r in roads:\n",
    "            self.e[r[0]].append(r[1])\n",
    "            self.e[r[1]].append(r[0])\n",
    "\n",
    "        self.isCut = [False] * n\n",
    "        self.dfn = [0] * n\n",
    "        self.low = [0] * n\n",
    "        self.tarjan(self.S)\n",
    "\n",
    "        # 整张图是一个双连通分量，选择整张图权值最小的点即可\n",
    "        if len(self.dcc) == 1:\n",
    "            return min(cost)\n",
    "\n",
    "        vec = []\n",
    "        for c in self.dcc:\n",
    "            cnt = 0\n",
    "            mn = float('inf')\n",
    "            for x in c:\n",
    "                if self.isCut[x]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    mn = min(mn, cost[x])\n",
    "\n",
    "            # 该双连通分量只和一个割点相连，是缩点形成的树的叶子节点\n",
    "            if cnt == 1:\n",
    "                vec.append(mn)\n",
    "        vec.sort()\n",
    "\n",
    "        ans = sum(vec[:-1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        n = len(cost)\n",
    "        G = [[] for i in range(n)]\n",
    "        for i,j in roads:\n",
    "            G[i].append(j)\n",
    "            G[j].append(i)\n",
    "        low = [n] * n\n",
    "        seen = {-1: -1}\n",
    "        cut = [0] * n\n",
    "        res = []\n",
    "        inf = float('inf')\n",
    "\n",
    "        def tarjan(i, pre):\n",
    "            seen[i] = len(seen) + 1\n",
    "            children = 0\n",
    "            min_cost = inf\n",
    "            count_cut = 0\n",
    "            for j in G[i]:\n",
    "                if j in seen:\n",
    "                    low[i] = min(low[i], seen[j])\n",
    "                    continue\n",
    "                children += 1\n",
    "                cur_cost, cur_cut = tarjan(j, i)\n",
    "                low[i] = min(low[i], low[j])\n",
    "                if seen[i] <= low[j]:\n",
    "                    if i != root or children > 1:\n",
    "                        cut[i] = 1\n",
    "                        cost[i] = inf\n",
    "                if i == root or seen[i] > low[j]:\n",
    "                    min_cost = min(min_cost, cur_cost)\n",
    "                    count_cut += cur_cut\n",
    "\n",
    "            min_cost = min(min_cost, cost[i])\n",
    "            count_cut += cut[i] > 0\n",
    "\n",
    "            if count_cut + (i != root) < 2 and seen[pre] <= low[i] and cut[i] == 0:\n",
    "                res.append(min_cost)\n",
    "            return [min_cost, count_cut]\n",
    "\n",
    "        tarjan(root:= 0, -1)\n",
    "        return sum(res) - max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        def tarjan(node: int, parent: int):\n",
    "            nonlocal seq\n",
    "            low[node] = ids[node] = seq\n",
    "            seq += 1\n",
    "            cnt = 0\n",
    "            for child in graph[node]:\n",
    "                # if child == parent:\n",
    "                #     continue\n",
    "                if low[child] < 0:\n",
    "                    tarjan(child, node)\n",
    "                    cnt += 1\n",
    "                    low[node] = min(low[node], low[child])\n",
    "                    if low[child] >= ids[node]:\n",
    "                        cut_points[node] = True\n",
    "                else:\n",
    "                    low[node] = min(low[node], ids[child])\n",
    "            if parent == -1:\n",
    "                cut_points[node] = cnt > 1\n",
    "\n",
    "        def dfs(node: int, parent: int) -> int:\n",
    "            result = cost[node]\n",
    "            for child in graph[node]:\n",
    "                if child == parent or seen[child] or cut_points[child]:\n",
    "                    if cut_points[child]:\n",
    "                        touched.add(child)\n",
    "                    continue\n",
    "                seen[child] = True \n",
    "                result = min(dfs(child, node), result)\n",
    "            return result\n",
    "\n",
    "        n = len(cost)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in roads:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ids = [0] * n\n",
    "        seq = 1\n",
    "        low = [-1] * n\n",
    "        cut_points = [False] * n\n",
    "        seen = [False] * n\n",
    "        tarjan(0, -1)\n",
    "        # tj(0)\n",
    "        # print(low, ids)\n",
    "        # print(cut_points)\n",
    "        result = []\n",
    "        touched = set()\n",
    "        for i in range(n):\n",
    "            if seen[i] or cut_points[i]:\n",
    "                continue\n",
    "            touched.clear()\n",
    "            a = dfs(i, -1)\n",
    "            if len(touched) < 2:\n",
    "                result.append(a)\n",
    "        # print(result)\n",
    "        if len(result) > 1:\n",
    "            return sum(result) - max(result)\n",
    "        return min(cost)#result[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        def tarjan(node: int, parent: int):\n",
    "            nonlocal seq\n",
    "            low[node] = ids[node] = seq\n",
    "            seq += 1\n",
    "            cnt = 0\n",
    "            for child in graph[node]:\n",
    "                if child == parent:\n",
    "                    continue\n",
    "                if low[child] < 0:\n",
    "                    tarjan(child, node)\n",
    "                    cnt += 1\n",
    "                    if low[child] >= ids[child] and node != 0:\n",
    "                        cut_points[node] = True\n",
    "                else:\n",
    "                    low[node] = min(low[node], low[child])\n",
    "                low[node] = min(low[node], low[child])\n",
    "            # if all([low[child] < ids[node] for child in graph[node] if child != parent]):\n",
    "            #   cut_points[node] = 0\n",
    "            # if cnt > 0 and low[node] == ids[node]:\n",
    "            #   cut_points[node] = True\n",
    "            if parent == -1:\n",
    "                cut_points[node] = cnt > 1\n",
    "\n",
    "        def tj(node: int):\n",
    "            nonlocal seq\n",
    "            low[node] = 2** 32\n",
    "            ids[node] = seq\n",
    "            seq += 1\n",
    "\n",
    "            children = 0\n",
    "            for child in graph[node]:\n",
    "                if ids[child] > 0:\n",
    "                    low[node] = min(low[node], ids[child])\n",
    "                    continue\n",
    "                children += 1\n",
    "                tj(child)\n",
    "                low[node] = min(low[node], low[child])\n",
    "                if ids[node] <= low[child]:\n",
    "                    cut_points[node] |= (node != 0 or children > 1)\n",
    "            # if node == 0 and children > 1:\n",
    "            #     cut_points[0] = True\n",
    "\n",
    "        def dfs(node: int, parent: int) -> int:\n",
    "            # return 0\n",
    "            result = cost[node]\n",
    "            for child in graph[node]:\n",
    "                if child == parent or seen[child] or cut_points[child]:\n",
    "                    if cut_points[child]:\n",
    "                        touched.add(child)\n",
    "                    continue\n",
    "                seen[child] = True \n",
    "                result = min(dfs(child, node), result)\n",
    "            return result\n",
    "\n",
    "        n = len(cost)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in roads:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ids = [0] * n\n",
    "        seq = 1\n",
    "        low = [-1] * n\n",
    "        cut_points = [False] * n\n",
    "        seen = [False] * n\n",
    "        # tarjan(0, -1)\n",
    "        tj(0)\n",
    "        print(low, ids)\n",
    "        print(cut_points)\n",
    "        result = []\n",
    "        touched = set()\n",
    "        for i in range(n):\n",
    "            if seen[i] or cut_points[i]:\n",
    "                continue\n",
    "            touched.clear()\n",
    "            a = dfs(i, -1)\n",
    "            if len(touched) < 2:\n",
    "                result.append(a)\n",
    "        print(result)\n",
    "        if len(result) > 1:\n",
    "            return sum(result) - max(result)\n",
    "        return min(cost)#result[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        def tarjan(node: int, parent: int):\n",
    "            nonlocal seq\n",
    "            low[node] = ids[node] = seq\n",
    "            seq += 1\n",
    "            cnt = 0\n",
    "            for child in graph[node]:\n",
    "                # if child == parent:\n",
    "                #     continue\n",
    "                if low[child] < 0:\n",
    "                    tarjan(child, node)\n",
    "                    cnt += 1\n",
    "                    low[node] = min(low[node], low[child])\n",
    "                    if low[child] >= ids[node]:\n",
    "                        cut_points[node] = True#(parent != -1 or children > 1)#True\n",
    "                else:\n",
    "                    low[node] = min(low[node], ids[child])\n",
    "                \n",
    "            # if all([low[child] < ids[node] for child in graph[node] if child != parent]):\n",
    "            #   cut_points[node] = 0\n",
    "            # if cnt > 0 and low[node] == ids[node]:\n",
    "            #   cut_points[node] = True\n",
    "            if parent == -1:\n",
    "                cut_points[node] = cnt > 1\n",
    "\n",
    "        def tj(node: int):\n",
    "            nonlocal seq\n",
    "            low[node] = ids[node] = seq#2** 32\n",
    "            seq += 1\n",
    "            children = 0\n",
    "            for child in graph[node]:\n",
    "                if ids[child] > 0:\n",
    "                    low[node] = min(low[node], ids[child])\n",
    "                    continue\n",
    "                children += 1\n",
    "                tj(child)\n",
    "                low[node] = min(low[node], low[child])\n",
    "                if ids[node] <= low[child]:\n",
    "                    cut_points[node] |= (node != 0 or children > 1)\n",
    "            # if node == 0 and children > 1:\n",
    "            #     cut_points[0] = True\n",
    "\n",
    "        def dfs(node: int, parent: int) -> int:\n",
    "            # return 0\n",
    "            result = cost[node]\n",
    "            for child in graph[node]:\n",
    "                if child == parent or seen[child] or cut_points[child]:\n",
    "                    if cut_points[child]:\n",
    "                        touched.add(child)\n",
    "                    continue\n",
    "                seen[child] = True \n",
    "                result = min(dfs(child, node), result)\n",
    "            return result\n",
    "\n",
    "        n = len(cost)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in roads:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ids = [0] * n\n",
    "        seq = 1\n",
    "        low = [-1] * n\n",
    "        cut_points = [False] * n\n",
    "        seen = [False] * n\n",
    "        tarjan(0, -1)\n",
    "        # tj(0)\n",
    "        print(low, ids)\n",
    "        print(cut_points)\n",
    "        result = []\n",
    "        touched = set()\n",
    "        for i in range(n):\n",
    "            if seen[i] or cut_points[i]:\n",
    "                continue\n",
    "            touched.clear()\n",
    "            a = dfs(i, -1)\n",
    "            if len(touched) < 2:\n",
    "                result.append(a)\n",
    "        print(result)\n",
    "        if len(result) > 1:\n",
    "            return sum(result) - max(result)\n",
    "        return min(cost)#result[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        n = len(cost)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in roads:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        clock = 0\n",
    "        dfn = [0] * n\n",
    "        low = [0] * n\n",
    "        vis = [False] * n\n",
    "        flag = [False] * n\n",
    "\n",
    "        def tarjan(u, fa):\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            child = 0\n",
    "            vis[u] = True\n",
    "            dfn[u] = low[u] = clock\n",
    "            for v in g[u]:\n",
    "                if not vis[v]:\n",
    "                    child += 1\n",
    "                    tarjan(v, u)\n",
    "                    low[u] = min(low[u], low[v])\n",
    "                    if fa != u and low[v] >= dfn[u] and not flag[u]:\n",
    "                        flag[u] = True\n",
    "                elif v != fa:\n",
    "                    low[u] = min(low[u], dfn[v])\n",
    "            if fa == u and child > 1 and not flag[u]:\n",
    "                flag[u] = True\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     if not vis[i]:\n",
    "        #         tarjan(i, i)\n",
    "        tarjan(0, 0)\n",
    "\n",
    "        def bfs(x):\n",
    "            ret = cost[x]\n",
    "            cv = set()\n",
    "            # cv means cut_vertex\n",
    "            q = deque([x])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if flag[y]:\n",
    "                        cv.add(y)\n",
    "                    elif cost[y]:\n",
    "                        ret = min(ret, cost[y])\n",
    "                        cost[y] = 0\n",
    "                        q.append(y)\n",
    "            return ret if len(cv) < 2 else 0\n",
    "\n",
    "        ans = list()\n",
    "        for i in range(n):\n",
    "            if not flag[i] and cost[i]:\n",
    "                a = bfs(i)\n",
    "                if a:\n",
    "                    ans.append(a)\n",
    "\n",
    "        return ans[0] if len(ans) == 1 else sum(ans) - max(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minimumCost(self, cost, roads):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :type roads: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(cost)\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        cnt = 0\n",
    "        num = 0\n",
    "        count = defaultdict(list)\n",
    "        st = []\n",
    "        low = [0 for _ in range(n)]\n",
    "        dfn = [0 for _ in range(n)]\n",
    "        is_cut = [False for _ in range(n)]\n",
    "        vec = []\n",
    "        for a,b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        def tarjan(x):\n",
    "            nonlocal cnt\n",
    "            nonlocal low\n",
    "            nonlocal dfn\n",
    "            nonlocal num\n",
    "            cnt += 1\n",
    "            low[x] = dfn[x] = cnt\n",
    "            flag =  0\n",
    "            st.append(x)\n",
    "            for nei in g[x]:\n",
    "                if dfn[nei] == 0:\n",
    "                    tarjan(nei)\n",
    "                    low[x] = min(low[x],low[nei])\n",
    "                    if low[nei] >= dfn[x]:\n",
    "                        flag += 1\n",
    "                        num += 1\n",
    "                        if x != 0 or flag > 1:\n",
    "                            is_cut[x] = True\n",
    "                        while True:\n",
    "                            cur = st.pop()\n",
    "                            count[num].append(cur)\n",
    "                            if cur == nei:\n",
    "                                break\n",
    "                        count[num].append(x)\n",
    "                else:\n",
    "                    low[x] = min(low[x],dfn[nei])\n",
    "        tarjan(0)\n",
    "\n",
    "        if num == 1:\n",
    "            ans = 0x3f3f3f3f\n",
    "            for x in  cost:\n",
    "                ans = min(x,ans)\n",
    "            return ans\n",
    "        for i in range(1,num + 1):\n",
    "            ct = 0\n",
    "            mn = 0x3f3f3f3f\n",
    "            for x in count[i]:\n",
    "                if is_cut[x]:\n",
    "                    ct += 1\n",
    "                else:\n",
    "                    mn = min(mn,cost[x])\n",
    "            if ct == 1:\n",
    "                vec.append(mn)\n",
    " \n",
    "        vec.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(vec) - 1):\n",
    "            ans += vec[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "\n",
    "        def tarjan(x: int) -> None:\n",
    "\n",
    "            nonlocal dfs_clock\n",
    "\n",
    "            low[x] = dfn[x] = dfs_clock\n",
    "\n",
    "            dfs_clock += 1\n",
    "\n",
    "            stk.append(x)\n",
    "\n",
    "            child = 0\n",
    "\n",
    "            flag = 0\n",
    "\n",
    "            for y in adjvex[x]:\n",
    "\n",
    "                if dfn[y] == 0:\n",
    "\n",
    "                    tarjan(y)\n",
    "\n",
    "                    low[x] = min(low[x], low[y])\n",
    "\n",
    "                    if low[y] >= dfn[x]:\n",
    "\n",
    "                        flag += 1\n",
    "\n",
    "                        if x != root or flag > 1:\n",
    "\n",
    "                            is_cut[x] = True\n",
    "\n",
    "                        \n",
    "\n",
    "                        t = stk.pop()\n",
    "\n",
    "                        dcc.append([])\n",
    "\n",
    "                        dcc[-1].append(t)\n",
    "\n",
    "                        while t != y:\n",
    "\n",
    "                            t = stk.pop()\n",
    "\n",
    "                            dcc[-1].append(t)\n",
    "\n",
    "                        dcc[-1].append(x)\n",
    "\n",
    "                else:\n",
    "\n",
    "                    low[x] = min(low[x], dfn[y])\n",
    "\n",
    "\n",
    "\n",
    "        n = len(cost)\n",
    "\n",
    "        if n == 1:\n",
    "\n",
    "            return cost[0]\n",
    "\n",
    "        \n",
    "\n",
    "        adjvex = defaultdict(list)\n",
    "\n",
    "        for x, y in roads:\n",
    "\n",
    "            adjvex[x].append(y)\n",
    "\n",
    "            adjvex[y].append(x)\n",
    "\n",
    "\n",
    "\n",
    "        root = 0\n",
    "\n",
    "        dfn = [0 for _ in range(n)]\n",
    "\n",
    "        low = [0 for _ in range(n)]\n",
    "\n",
    "        dfs_clock = 1\n",
    "\n",
    "        is_cut = [False for _ in range(n)]\n",
    "\n",
    "        stk = collections.deque()\n",
    "\n",
    "        dcc = []\n",
    "\n",
    "        \n",
    "\n",
    "        tarjan(root)\n",
    "\n",
    "    \n",
    "\n",
    "        if len(dcc) == 1:\n",
    "\n",
    "            res = 10 ** 9\n",
    "\n",
    "            for co in cost:\n",
    "\n",
    "                res = min(res, co)\n",
    "\n",
    "            return res\n",
    "\n",
    "        \n",
    "\n",
    "        leaf = []\n",
    "\n",
    "        for dc in dcc:\n",
    "\n",
    "            cut_cnt = 0\n",
    "\n",
    "            min_cost = 10 ** 9\n",
    "\n",
    "            for x in dc:\n",
    "\n",
    "                if is_cut[x] == True:\n",
    "\n",
    "                    cut_cnt += 1\n",
    "\n",
    "                else:\n",
    "\n",
    "                    min_cost = min(min_cost, cost[x])\n",
    "\n",
    "            if cut_cnt == 1:\n",
    "\n",
    "                leaf.append(min_cost)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        leaf.sort()\n",
    "\n",
    "        for i in range(len(leaf) - 1):\n",
    "\n",
    "            res += leaf[i]\n",
    "\n",
    "    \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        n = len(cost)\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for i, j in roads:\n",
    "            neighbors[i].append(j)\n",
    "            neighbors[j].append(i)\n",
    "        # tarjan\n",
    "        dfn, low = [-1] * n, [-1] * n\n",
    "        t = [0]\n",
    "        cut = [False] * n\n",
    "        def dfs(x, fa):\n",
    "            dfn[x] = low[x] = t[0]\n",
    "            childen = 0\n",
    "            for y in neighbors[x]:\n",
    "                if y == fa: continue\n",
    "                if dfn[y] != -1:\n",
    "                    low[x] = min(low[x], dfn[y])\n",
    "                else:\n",
    "                    t[0] += 1\n",
    "                    dfs(y, x)\n",
    "                    childen += 1\n",
    "                    low[x] = min(low[x], low[y])\n",
    "                    if fa == -1 and childen > 1:\n",
    "                        cut[x] = True\n",
    "                    if fa != -1 and low[y] >= dfn[x]:\n",
    "                        cut[x] = True\n",
    "        dfs(0, -1)\n",
    "        # calc connected\n",
    "        parent, rank = list(range(n)), [0] * n\n",
    "        def myFind(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = myFind(parent[x])\n",
    "            return parent[x]\n",
    "        def myUnion(x, y):\n",
    "            px, py = myFind(x), myFind(y)\n",
    "            if px == py: return\n",
    "            if rank[px] > rank[py]:\n",
    "                parent[py] = px\n",
    "            elif rank[px] < rank[py]:\n",
    "                parent[px] = py\n",
    "            else:\n",
    "                parent[py] = px\n",
    "                rank[px] += 1\n",
    "            return\n",
    "        for i, j in roads:\n",
    "            if cut[i] or cut[j]: continue\n",
    "            myUnion(i, j)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            if not cut[i]:\n",
    "                pi = myFind(i)\n",
    "                d[pi] = min(d.get(pi, 10 ** 9), cost[i])\n",
    "        deg = {}\n",
    "        for i, j in roads:\n",
    "            pi, pj = myFind(i), myFind(j)\n",
    "            if pi not in deg: deg[pi] = set()\n",
    "            if pj not in deg: deg[pj] = set()\n",
    "            if pi == pj: continue\n",
    "            deg[pi].add(pj)\n",
    "            deg[pj].add(pi)\n",
    "        val = []\n",
    "        for k, v in d.items():\n",
    "            if len(deg[k]) < 2:\n",
    "                val.append(v)\n",
    "        if len(val) == 1:\n",
    "            return val[0]\n",
    "        return sum(val) - max(val)                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        n = len(cost)\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for i, j in roads:\n",
    "            neighbors[i].append(j)\n",
    "            neighbors[j].append(i)\n",
    "        # tarjan\n",
    "        dfn, low = [-1] * n, [-1] * n\n",
    "        t = [0]\n",
    "        cut = [False] * n\n",
    "        def dfs(x, fa):\n",
    "            dfn[x] = low[x] = t[0]\n",
    "            childen = 0\n",
    "            for y in neighbors[x]:\n",
    "                if y == fa: continue\n",
    "                if dfn[y] != -1:\n",
    "                    low[x] = min(low[x], dfn[y])\n",
    "                else:\n",
    "                    t[0] += 1\n",
    "                    dfs(y, x)\n",
    "                    childen += 1\n",
    "                    low[x] = min(low[x], low[y])\n",
    "                    if fa == -1 and childen > 1:\n",
    "                        cut[x] = True\n",
    "                    if fa != -1 and low[y] >= dfn[x]:\n",
    "                        cut[x] = True\n",
    "        dfs(0, -1)\n",
    "        # calc connected\n",
    "        parent, rank = list(range(n)), [0] * n\n",
    "        def myFind(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = myFind(parent[x])\n",
    "            return parent[x]\n",
    "        def myUnion(x, y):\n",
    "            px, py = myFind(x), myFind(y)\n",
    "            if px == py: return\n",
    "            if rank[px] > rank[py]:\n",
    "                parent[py] = px\n",
    "            elif rank[px] < rank[py]:\n",
    "                parent[px] = py\n",
    "            else:\n",
    "                parent[py] = px\n",
    "                rank[px] += 1\n",
    "            return\n",
    "        for i, j in roads:\n",
    "            if cut[i] or cut[j]: continue\n",
    "            myUnion(i, j)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            if not cut[i]:\n",
    "                pi = myFind(i)\n",
    "                d[pi] = min(d.get(pi, 10 ** 9), cost[i])\n",
    "        deg = {}\n",
    "        for i, j in roads:\n",
    "            pi, pj = myFind(i), myFind(j)\n",
    "            if pi not in deg: deg[pi] = set()\n",
    "            if pj not in deg: deg[pj] = set()\n",
    "            if pi == pj: continue\n",
    "            deg[pi].add(pj)\n",
    "            deg[pj].add(pi)\n",
    "        val = []\n",
    "        for k, v in d.items():\n",
    "            print(f\"k{k}\")\n",
    "            if len(deg[k]) < 2:\n",
    "                val.append(v)\n",
    "        if len(val) == 1:\n",
    "            return val[0]\n",
    "        return sum(val) - max(val)                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:\n",
    "        n = len(cost)\n",
    "        G = [set() for i in range(n)]\n",
    "        for i,j in roads:\n",
    "            G[i].add(j)\n",
    "            G[j].add(i)\n",
    "        low = [n] * n\n",
    "        seen = {}\n",
    "        cut = [0] * n\n",
    "\n",
    "        def tarjan(i):\n",
    "            seen[i] = len(seen) + 1\n",
    "            children = 0\n",
    "            for j in G[i]:\n",
    "                if j in seen:\n",
    "                    low[i] = min(low[i], seen[j])\n",
    "                    continue\n",
    "                children += 1\n",
    "                tarjan(j)\n",
    "                low[i] = min(low[i], low[j])\n",
    "                if seen[i] <= low[j]:\n",
    "                    cut[i] += i != root or children > 1\n",
    "\n",
    "        root = 1\n",
    "        tarjan(root)\n",
    "        seen_cut = set()\n",
    "        res = []\n",
    "        done = [0] * n\n",
    "\n",
    "        def dfs2(i):\n",
    "            done[i] = 1\n",
    "            min_cost = cost[i]\n",
    "            for j in G[i]:\n",
    "                if done[j]: continue\n",
    "                if cut[j]:\n",
    "                    seen_cut.add(j)\n",
    "                    continue\n",
    "                min_cost = min(min_cost, dfs2(j))\n",
    "            return min_cost\n",
    "            \n",
    "        for i in range(n):\n",
    "            if done[i] or cut[i]: continue\n",
    "            seen_cut = set()\n",
    "            min_cost = dfs2(i)\n",
    "            if len(seen_cut) < 2:\n",
    "                res.append(min_cost)\n",
    "        return sum(res) - max(res) if len(res) > 1 else res[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
